package com.lagou.code;

/**
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
 * 有的金矿储量是200kg黄金，需要3个工人来挖掘……
 * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 * @author yzh
 */
public class GetBestGoldIncomeTask {

    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益为：" + getBestGoldIncome(w, p, g));
    }

    /**
     * 获得金矿最优收益
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿数量
     * @return 最优收益
     */
    public static int getBestGoldIncome(int w, int[] p, int[] g){
        //声明结果数组
        int[] results = new int[w + 1];
        //遍历并封装结果数组
        for (int i = 1; i <= g.length; i++){
            for (int j = w; j >= 1; j--){
                if (j >= p[i-1]){
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回结果数组最后一个元素
        return results[w];
    }
}